This application claims the benefit of a Japanese Patent Applications No. 2001-157727 filed May 25, 2001, No. 2001-161811 filed May 30, 2001 and No. 2001-401070 filed Dec. 28, 2001, in the Japanese Patent Office, the disclosures of which are hereby incorporated by reference.
1. Field of the Invention
The present invention generally relates to image encoding methods, image encoding apparatuses and storage media, and more particularly to an image encoding method for encoding an image having a periodic property such as a dither image using a dither matrix, an image encoding apparatus which employs such an image encoding method to encode an image, and a computer-readable storage medium which stores a program for causing a computer to carry out such an image encoding method.
2. Description of the Related Art
When outputting image data with respect to an image processing apparatus having a small number of gradation levels that can be represented per pixel, a systematic dither method is used in most cases. For example, in a printer or facsimile machine which prints depending on existence of dots, it is normally only possible to represent 2 gradation levels per pixel. When representing a halftone such as a photograph on such an image processing apparatus, an image created by the systematic dither method is used as shown in FIGS. 1A through 1C.
FIGS. 1A through 1C are diagrams for explaining an example of a dither process using the systematic dither method. FIG. 1A shows an example of multi gradation level (multilevel) data prior to the dither process. FIG. 1B shows an example of a dither matrix applied to the multilevel data shown in FIG. 1A. In addition, FIG. 1C shows an example of image data after applying the dither matrix shown in FIG. 1B to the multilevel data shown in FIG. 1A. The dither process compares the original multilevel data shown in FIG. 1A and the values (threshold values) of the dither matrix shown in FIG. 1B, and outputs the compared result as shown in FIG. 1C. Because the dither matrix is used repeatedly, the image created by the dither process has the same periodic property as the dither matrix. This periodic property is particularly conspicuous in the case of images having a large number of low-frequency components, such as photographs.
As a technique for compressing and encoding the dither image having the periodic property, there is a known technique which focuses on the dither matrix which is used to create the dither image. Such a technique is proposed in a Japanese Laid-Open Patent Application No. 55-050776, for example, and data of pixels of the same phase in the dither matrix are collected and encoded. Data of adjacent pixels of the same phase have a strong tendency of taking the same value, because the image data normally includes a large number of low-frequency components. In a case where the original multilevel data are the same for all pixels (only D.C. components exist), the data of the pixels of the same phase of the dither matrix always have the same value. Due to this general tendency, it is possible to obtain a high compression rate when a run length encoding, for example, is carried out after collecting the data of the pixels of the same phase of the dither matrix.
However, according to the technique proposed in the Japanese Laid-Open Patent Application No. 55-050776, the data of the pixels of the same phase are collected for each pixel position, and there was a problem in that the processing speed is slow. For example, when carrying out the encoding by collecting data of 16 pixels of the same phase, it becomes necessary to make 16 memory accesses if the data of only one pixel of a certain phase can be obtained in one memory access. For this reason, it is only possible to encode the data of one pixel during the time of one memory access. In order to increase the processing speed, it was necessary to either prepare a register which can hold the data of the pixels of all phases obtained by 16 memory accesses or, to increase the circuit scale so that it is possible to obtain the data of the 16 pixels of the same phase in one memory access.